# -*- coding: UTF-8 -*-
import itertools
import sys

# 将一堆正整数分为2组，要求2组的和相差最小。
#例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。
#暴力破解法
def divIntArr(data):
    total = sum(data)
    diff = total
    for i in range(1, len(data)):
        for value in itertools.combinations(data, i):
            diff_sub = sum(value)
            diff_sub = total - 2 * diff_sub
            if (diff_sub >= 0 and diff_sub < diff):
                diff = diff_sub
    return diff


#dp算法解决正整数分为2组
def divIntArr_dp(data):
    total = sum(data)
    diff = total
    ls = [ None for x in range(0,len(data) + 1 )]
    ls[0] = set(0)
    for i in range(1,len(data) + 1):
        preset = set(map(lambda x: x+data[i])) | set(data[i])
        now = ls[i-1]
        ls[i] = preset | now
    for value in ls[len(data)]:
        if( total - 2*value >= 0 and total - 2*value < diff):
            diff = total - 2*value   
    return diff
#背包问题1    
#有n个重量和价值分别为weights(list),values(list)的物品；背包最大负重为W，求能用背包装下的物品的最大价值？
#输入：n =4 
#weight=2, 1, 3, 2
#value =3, 2, 4, 2
#W=5
#输出=7
def bagProblem(weights,values,W):
    dp = [ [0 for x in range(0,W+1)] for x in range(0,len(weights))]
    dp[0][0] = 0
    for i in range(1,W+1):
        if ( values[0] <= i ):
            dp[0][i] = values[0]
    for i in range(1,len(weights)):
        for j in range(1,W+1):
            iNotSelect = dp[i-1][j]
            if(j >= weights[i]):
                iSelected = dp[i-1][j-weights[i]]+values[i]
            else :
                iSelected = 0
            dp = max(notSelect,selected)         
    
    return  dp[len(weights)-1][W]       
#逆序与全排列
#url http://www.cnblogs.com/saltless/archive/2011/06/01/2065619.html
#在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。
#一个排列中逆序的总数就称为这个排列的逆序数。
#如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。
#主要状态转移方程 f(n+1,m)=f(n,m)+f(n,m-1)+…+f(n,m-n)
def  backward_sequence_range(n,m):
    if(  m > n *(n-1)/2 or m < 0):
        return 0
    if ( m > n*(n-1)/2 ):
        m = n*(n-1)/2 - m 
    if ( m == 1):
        return n-1
    #dp为二维数组,dp[i][j]表示i个元素组成逆序数为j时的排列数目
    dp = [[ 0 for x in range(0,m+1)] for x in range(0,n+1)]   
    #初始化dp[0...n][0]    
    for i in range(0,n+1):
        dp[i][0] = 1
    #使用动态规划计算dp[i][j]
    for i in range(1,n+1):
        for j in range(1,m+1):
            #根据性质f(n,m) = f(n,C(n,2)-m)，减少计算量
            if (j <= i*(i-1)//4):
                for x in range(max(j-i,0),j+1):
                    dp[i][j] += dp[i-1][x]                
            elif (j > i*(i-1)//4 and j <= i*(i-1)//2):
                dp[i][j] = dp[i][(i*(i-1)//2)-j]
            else :
                break
    return dp[n][m]
# 石头归并v1,线性归并
# url : http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1021
# 该解法为N3，N2的解法涉及到 动态规划原理的四边形不等式加速原理，暂时未看懂
# dp[i][j]表示从第i个石子到第j个石子的归并结果
# ref : http://blog.csdn.net/acdreamers/article/details/18039073
def merge_stones_v1(stones):
    dp = [ [ 0 for x in range(0,len(stones))] for x in range(0,len(stones))]
    sum_i = [ 0 for x in range (0,len(stones))]    
    # 求 sum 数组组合
    sum_i[0] = stones[0]
    for i in range(1,len(stones)):
        sum_i[i] = sum_i[i-1] + stones[i]
    #v表示m(i,j)中 j-i 的值
    for v in range(1,len(stones)):    
        #i表示m(i,j)中的起始点
        for i in range(0,len(stones)-v):
            j = i + v
            dp[i][j] = sys.maxint
            if(i > 0):
                temp = sum_i[j] - sum_i[i-1]
            else:
                temp = sum_i[j]
            for k in range(i,j):
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j] + temp)
    return dp[0][len(stones) - 1]
#石头归并v2,环型归并
#URL : http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1022
#该解法为N3，N2的解法涉及到 动态规划原理的四边形不等式加速原理，暂时未看懂
#dp[i][j]表示从第i个石子到第(i+j)%n的归并结果
#ref :http://blog.csdn.net/acdreamers/article/details/18039073
def merge_stones_v2(stones):
    sums = [ 0 for x in range(0,len(stones))]
    sums[0] = stones[0]
    for i in range(1,len(stones)):
        sums[i] = stones[i] - sums[i-1]
    dp = [ [ 0 for x in range(0,len(stones)-1)] for x in range(0,len(stones)) ]
    for i in range(0,len(stones)):
        dp[i][0] = 0
    for v in range(1,len(stones)-1):
        for i in range(0,len(stones)):
            dp[i][v] = sys.maxint
            temp = self.merege_stones_v2_get_sum(sums,i,v)
            for k in range(1,v):
                dp[i][v] = min(dp[i][v],dp[i][k]+dp[(i+k+1)%len(stones)][j-k-1] + self.merege_stones_v2_get_sum(sums,i,j))

    min_merge = dp[0][len(stones)-2]
    for i in range(1,len(stones)):
        if dp[i][len(stones) - 2]:
            min_merge = dp[i][len(stones) - 2]
    return min_merge
#@param sums 和数组
#@param i 起始位置
#@param j 步长
#@return 从第i位置开始j步的总和
def merege_stones_v2_get_sum(sums,i,j):
    if i < 1:
        sum_i = 0
    else :
        sum_i = sum[i-1]
    if i + j < len(sums):
        return sum[i+j] - sum_i
    else:
        return sum[len(sums)-1]-sum_i + sum[(i+j)%len(sums)]

#最长子数组和,有n3,nlog2n和n的时间复杂度解法
#@param nums 整形数组
#@return integer
def max_sub_arr_sum(nums):
    this_sum,max_sum = 0,0
    for i in range(0,len(nums)):
        this_sum += nums[i]
        if this_sum > max_sum :
            max_sum = this_sum
        elif this_sum < 0 :
            this_sum = 0
    return max_sum

    